// x的平方根

package Leetcode;

class solution_069 {
    public int mySqrt(int x) {
        if (x <= 1)
            return x;
        int i;
        for (i = 1; i <= x / 2 && i <= 46340; i++) {
            if (i * i == x)
                return i;
            else if (i * i > x)
                return i - 1;
        }
        return i - 1;
    }
}

// 使用牛顿迭代
public class Solution069 {
    public int mySqrt(int x) {
        if (x == 0)
            return 0;
        double C = x;
        double x0 = x;
        while (true) {
            double xi = 1 / (2 * x0) * (x0 * x0 + C);
            if (Math.abs(xi - x0) < 1e-7)
                break;
            x0 = xi;
        }
        return (int) x0;
    }
}
